The present invention relates to a method and apparatus for recognizing an identifier that is entered into a system by a user, and in particular, to a method and apparatus that matches an input identifier to one of a plurality of reference identifiers by a process that includes generating a plurality of option identifiers.
Most institutions, such as banks and department stores, allow customers to access over the telephone a wide variety of services and account information. Before the advent of touch-tone telephones, a customer would obtain these services and information through interacting with a live operator. As touch-tone telephones became more prevalent in homes, these institutions began switching to automated customer-access systems. After dialing a telephone number, a customer using such systems would be asked to enter an account number or identifier. As used herein, the terms "account number" and "identifier" are used interchangeably, and they refer to a string of characters that may comprise a plurality of letters, numbers, or both. Furthermore, as used herein, an identifier may be used not only to identify a user, but also may be used as an identifier for identifying a particular product or service offered by an institution. In the first generation of automated customer-access systems, a user would enter such an identifier by sequentially pressing a series of keys provided on the telephone keypad. Each pressed key would correspond to a different character in the identifier. The pressing of these keys would produce a series of tones that would be provided over a telephone network to the institution. At the institution, the series of tones would be decoded to produce the entered identifier, and if the identifier entered by the user was determined to correspond to a valid identifier, then the user would be allowed to enter commands, again through the telephone keypad, that would provide access to whatever services would be offered by the institution.
The next generation of automated customer-access systems eliminates the use of telephone keypads to verify the identity of a valid user. Instead of entering an identifier through a telephone keypad, a user would be prompted to speak the identifier into the telephone handset. For example, the user may speak into the telephone the identifier "JB123E". The user's voice signal would be transmitted over the phone lines to the institution, which would employ a speech recognition system to produce a recognized identifier that is intended to correspond exactly to the identifier spoken by the user. This recognized identifier would then be compared to a plurality of reference identifiers maintained in memory, each reference identifier representing, for example, a valid account number. If the recognized identifier matched a reference identifier, then the recognized identifier would be treated as validly matching the input identifier; the system would then execute a transaction on the basis of the matched input identifier.
Nevertheless, such exact correspondence between an input identifier and a recognized identifier is quite difficult to attain, mostly due to the deterioration of voice signals that routinely occurs over conventional telephone lines. In particular, as a voice signal is transmitted to a remote location, conventional telephone lines introduce into such signals noise and restrictive band limitations. Such a deterioration present in a voice signal may cause a remote speech recognizer to produce a recognized output that does not correspond to the spoken identifier. Because of the limitations introduced into the voice signal by the telephone lines, the speech recognizer may confuse similar sounding letters and numbers. Thus, a speech recognizer may confuse the letter "A" with the number "8", the letter "K", or the letter "J". Similarly, the speech recognizer may confuse the letter "C" with the letter "D" or the number "3". For example, given that a user speaks the identifier "JB123E" into a telephone, the speech recognizer may produce "AE123D" as an output.
In order to improve the accuracy of such speech recognition systems, the invention of U.S. patent application Ser. No. 08/763,382 ("the '382 application") which is hereby incorporated by reference, performs a probabilistic determination that selects the reference identifier that most likely matches the input identifier. In order to perform this probabilistic determination, the system of the '382 application employs one or more confusion matrices, each confusion matrix being an arrangement of probability values that individually represent the probability that a particular input character will be recognized either as itself or as another character. For example, such a confusion matrix would store values representing the probability that an A spoken by a user would be recognized as either itself or as any other character, such as an 8, a J, a K, or a B. After producing a recognized identifier on the basis of the input identifier provided by the user, the system of the '382 application performs a character-by-character comparison between the recognized identifier and each reference identifier. In performing this comparison, the system of the '382 application uses the confusion matrix to determine the probability that, given a particular character of the recognized identifier, the character occupying the corresponding character position in the reference identifier under comparison would have been spoken by the user. This system then calculates an identifier recognition probability for each reference identifier on the basis of the confusion matrix values obtained during the comparison between each reference identifier and the recognized identifier. The reference identifier associated with the highest identifier recognition probability is then selected as the most likely match for the input identifier. For systems that store an exceedingly large number of reference identifiers, however, performing the above-described calculation for each reference identifier may involve undue delays and use an excessive amount of available processing resources. Accordingly, in systems that employ such a large amount of reference identifiers, a need exists to determine in a timely manner the most likely match for an input identifier without unduly expending available computing resources.